#include <iostream>

using namespace std;

template <class T,class K>
struct DATA
{
    K index;
    T data;
    DATA<T,K>* next;
};

template <class T,class K>
class DICTIONARY
{
public:
    DICTIONARY();
    ~ DICTIONARY();
    bool empty();
    int size();
    void insert(K key,T element);
    T find(K key);
    void erase(K key);
    void display();
private:
    DATA<T,K>* d;
};

template <class T,class K>
DICTIONARY<T,K>::DICTIONARY()
{
    d=(DATA<T,K>*)new DATA<T,K>;
    d->next=NULL;
};

template <class T,class K>
DICTIONARY<T,K>::~DICTIONARY()
{
    while(d->next!=NULL)
    {
        DATA<T,K>* temp=d;
        d=temp->next;
        free(temp); // FIXME: 建议用delete释放new出来的对象（new,delete配对使用，malloc，free配对使用）
    }
};

template <class T,class K>
bool DICTIONARY<T,K>::empty()
{
    if(d->next==NULL)
        return true;
    else return false;
};

template <class T,class K>
int DICTIONARY<T,K>::size()
{
    int n=0;
    DATA<T,K>* temp=d;
    while(temp->next!=NULL)
    {
        temp=temp->next;
        n++;
    }
    return n;
};

template <class T,class K>
void DICTIONARY<T,K>::insert(K key,T element)
{
    DATA<T,K>* temp=d;
    DATA<T,K>* ftemp=temp;
    while (key>temp->index&&temp->next!=NULL)
    {
        ftemp=temp;
        temp=temp->next;
    }

    if(key==temp->index)
    {
        temp->data=element;    //replace the same index
    }
    
    if(key<temp->index)
    {
        DATA<T,K>* trans=(DATA<T,K>*) new DATA<T,K>;    //insert with order(there is a bug that the DATA can't insert at the front of the last DATA);
        trans->index=key;
        trans->data=element;
        trans->next=ftemp->next;
        ftemp->next=trans;
    }
    else    //insert at the end when the index is the bigger than any list index;
    {
         DATA<T,K>* trans=(DATA<T,K>*) new DATA<T,K>;
        trans->index=key;
        trans->data=element;
        trans->next=temp->next;
        temp->next=trans;
    }
 };

template<class T,class K>
T DICTIONARY<T,K>::find(K key)
{
    DATA<T,K>* temp=d;

    while(key!=temp->index && temp->next!=NULL)
    {
        temp=temp->next;
    }

    if(temp->next==NULL)
    {
        cout<<"this is a wrong index"<<endl;
        return NULL;
    }
    else  
    {
        return temp->data;
    }
};

template<class T,class K>
void DICTIONARY<T,K>::display()
{
    DATA<T,K>* temp=d->next;
    while(temp!=NULL)
    {
        cout<<temp->index<<"  "<<temp->data<<"  ";
        temp=temp->next;
    }
    cout<<endl;
};

template<class T,class K>
void DICTIONARY<T,K>::erase(K key)
{
    DATA<T,K>* temp=d;
    while(temp->next->index < key)
    {
        temp=temp->next;
    }
    if(temp->next->index==key)
    {
        DATA<T,K>* temp1=temp;
        temp1=temp->next;
        temp->next=temp->next->next;
        free(temp1); 
    }
    else cout<<"this id a wrong index"<<endl;
};

int main()
{
    DICTIONARY<int, int> a;
    for(int i=1;i<6;i++)
    {
        a.insert(i,i*3);
    }

    cout<<a.size()<<endl;

    a.display();

    cout<<a.find(3)<<endl;

    a.erase(2);
    a.display();

    a.insert(8,6);
    a.display();

    a.insert(6,6);
    a.display();

    cout<<a.size();

    system("pause");
    return 0;
}


